#include <iostream>
#include <vector>

using namespace std;

template <class T>
void print_arr(T &nums)
{
    for (size_t i = 0; i < nums.size(); i++)
        cout << nums[i] << ",";
    cout << endl;
}


class Solution {
public:
    
    void merge(vector<int> &nums, int left, int mid, int right) {
        vector<int> tmp;
        int pl = left, pr = mid;
        while (pl < mid && pr <= right) {
            if (pl < mid && nums[pl] < nums[pr]) {
                tmp.push_back(nums[pl]);
                pl++;
            } else if (pr <= right) {
                tmp.push_back(nums[pr]);
                pr++;
            }
        }
        if (pl < mid)
            for (pl; pl < mid; pl++)
                tmp.push_back(nums[pl]);
        if (pr <= right)
            for (pr; pr <= right; pr++)
                tmp.push_back(nums[pr]);
        for (size_t i = 0; i < tmp.size(); i++) {
            nums[left+i] = tmp[i];
        }
    }

    void split(vector<int> &nums, int left, int right) {
        cout << "l" << left << "r" << right << endl;
        if (left == right)
            return;
        int mid = left + (right - left) / 2;
        split(nums, left, mid);
        split(nums, mid+1, right);

        merge(nums, left, mid+1, right);
        print_arr(nums);
    }

    void sort(vector<int> &nums) {
        split(nums, 0, nums.size()-1);
        //print_arr(test1);
    }
};


namespace CImplement {
    void print_arr(int nums[], int count) {
        for (size_t i = 0; i < count; i++)
            printf("%d, ", nums[i]);
        printf("\n");
    }

    void merge(int nums[], int l, int mid, int r) {
        int temp[r-l+1];
        int ptr = 0;
        int lp = l, rp = mid+1;

        while (lp <= mid && rp <= r) {
            if (nums[lp] < nums[rp])
                temp[ptr++] = nums[lp++];
            else
                temp[ptr++] = nums[rp++];
        }

        for (lp; lp <= mid; )
            temp[ptr++] = nums[lp++];

        for (rp; rp <= r; )
            temp[ptr++] = nums[rp++];

        for (int i = 0; i < r-l+1; i++) {
            nums[l+i] = temp[i];
        }
    }

    void split(int nums[], int l, int r) {
        int mid = l + (r-l)/2;
        if (r <= l)
            return;
        split(nums, l, mid);
        split(nums, mid+1, r);
        merge(nums, l, mid, r);
    }

    void sort(int nums[], int count) {
        split(nums, 0, count-1);
    }
};

int main(void)
{
    vector<int> nums = {10, 9, 11, 12, 8};
    //print_arr(nums);
    //(new Solution())->sort(nums);
    //print_arr(nums);

    int nums2[nums.size()];
    copy(nums.begin(), nums.end(), nums2);
    CImplement::print_arr(nums2, nums.size());
    CImplement::sort(nums2, nums.size());
    CImplement::print_arr(nums2, nums.size());
    return 0;
}